package basic.study.algorithms.solution.DynamicProgramming;

/**
 * @author Kevin
 * @date 2020/2/19 14:32
 * 设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
 */
public class minDistMatrix {
    private int minDist = Integer.MAX_VALUE;
    //首先敲出回溯的代码
    public void setMinDist(int i, int j, int dist, int[][] w, int n) {
        //到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
        if (i == n && j == n) {
            if (dist < minDist) minDist = dist;
            return ;
        }
        if (i < n) {//往下走，继续更新i=i+1，j=j
            setMinDist(i+1, j, dist+w[i][j], w, n);
        }
        if (j < n) {//往右走，继续更新i=i， j=j+1
            setMinDist(i, j+1, dist+w[i][j], w, n);
        }
    }
    //话递归树分析，如何去重
    //然后写出动态规划代码,状态转移表法
    public int minDIstDP(int[][] matrix, int n) {
        int[][] states = new int[n][n];
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += matrix[0][j];
            states[0][j] = sum;
        }
        sum = 0;
        for (int i = 0; i < n; i++) {
            sum += matrix[i][0];
            states[i][0] = sum;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                states[i][j] = matrix[i][j] + Math.min(states[i-1][j], states[i][j-1]);
            }
        }
        return states[n-1][n-1];
    }

    //状态转移方程法
    //下面我用递归加“备忘录”的方式，将状态转移方程翻译成来代码，你可以看看。对于另一种实现方式，跟状态转移表法的代码实现是一样的，只是思路不同。
    private int[][] matrix = {{1,3,5,9}, {2,1,3,4}, {5,2,6,7}, {6,8,4,3}};
    private int n = 4;
    private int[][] mem = new int[4][4];
    public int MinDist(int i, int j) {// 调用minDist(n-1, n-1);
        if (i == 0 && j == 0) return matrix[0][0];
        if (mem[i][j] > 0) return mem[i][j];//备忘录，不重复计算
        int minLeft = Integer.MAX_VALUE;
        if (j-1 >= 0) {
            minLeft = MinDist(i,j-1);
        }
        int minRight = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            minRight = MinDist(i-1, j);
        }

        int currMinDist = matrix[i][j] + Math.min(minLeft, minRight);
        mem[i][j] = currMinDist;
        return currMinDist;
    }
}
